---
title: "L2-004 这是二叉搜索树吗？"
created: 2025-11-28
tags:
  - 算法
---

# L2-004 这是二叉搜索树吗？

## 题目 [L2-004 这是二叉搜索树吗？](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805070971912192&page=1)

![[image-19b56b20.png]]

## 思路分析

![[image-664d258c.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

const int N=1010;

int pre[N];

vector<int> ans;

bool is_mirror=false;

void dfs(int l,int r){

	if(l>r)	return;

	int i = l+1,j=r;

	if(!is_mirror){

		while(i<=r && pre[i]<pre[l])	i++;

		while(j>=l+1 && pre[j]>=pre[l])	j--;

	}else{

		while(i<=r && pre[i]>=pre[l])	i++;

		while(j>=l+1 && pre[j]<pre[l])	j--;

	}

	if(abs(i-j)!=1)	return;

	dfs(l+1,j);

	dfs(i,r);

	ans.push_back(pre[l]);

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n;cin>>n;

	for(int i=0;i<n;i++)	cin>>pre[i];

	dfs(0,n-1);

	if(ans.size() != n){

		is_mirror = true;

		ans.clear();

		dfs(0,n-1);

	}

	if(ans.size() != n){

		cout<<"NO"<<endl;

	}else{

		cout<<"YES"<<endl;

		for(int i=0;i<n;i++){

			if(i)	cout<<" ";

			cout<<ans[i];

		}

	}

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-003 月饼|L2-003 月饼]] 🏠 [[00-天梯赛]] ➡️ [[L2-005 集合相似度|L2-005 集合相似度]]